package com.singzi.leetcode.jianzhiOffer;

public class T0063 {
    public static void main(String[] args) {
        int []a = {7,1,5,3,6,4};
        Solution00063 solution00063 = new Solution00063();
        System.out.println(solution00063.maximumDifference(a));
    }
}
class Solution00063 {
    public int maximumDifference(int[] nums) {

        int n = nums.length;
        int []maxNums = new int[n];
        int []minNums = new int[n];
        int maxNum = Integer.MIN_VALUE;
        int minNum = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if(nums[n-i-1] > maxNum) maxNum = nums[n - i - 1];
            maxNums[n - i - 1] = maxNum;
            if (nums[i] < minNum) minNum = nums[i];
            minNums[i] = minNum;
        }
        maxNum = 0;
        for (int i = 0; i < n; i++) {
            if(maxNums[i] - minNums[i] > maxNum) maxNum = maxNums[i] - minNums[i];
        }
        return maxNum;

    }
}